This invention relates to a method and apparatus for reproducing full-color images on output devices through electronic image processing and, more particularly, to a method and apparatus for improving the quality of the output of full-color images reproduced on output devices such as color printers and displays, for example, that reproduce colors using a comparatively small number of intensity or density levels of primary colorants by using halftoning techniques to combine the number of dots of each primary colorant so that an output display level, or dot level, is formed having the different colorant dots substantially homogeneously distributed.
In full-color images, the color value of each pixel may be specified by 24 bits which can uniquely specify each of over 16 million different colors. These images are typically displayed on output devices such as a color printer, for example, using primary colorants having a comparatively small number of intensity or density values to produce color.
For example, an ink jet color printer commonly combines cyan, magenta, and yellow inks, and optionally black ink, in varying proportions to produce the illusion of many of these 16 million colors when viewed at a normal viewing distance. The proportions of ink are varied by placing patterns of discrete amounts of each colorant over selected areas of the printed page.
As is common for a binary ink jet or laser printer, a dot of a specific colorant can either be placed or not placed at a given pixel location in a rectangular array. This produces a pattern that may be highly visible to the human eye.
Various halftoning algorithms have previously been used to produce patterns that are pleasing to the human eye. These algorithms have been traditionally applied independently for each colorant. While this results in dot patterns for each colorant being visually pleasing, the overall pattern of the dots is not normally pleasing when dots from all of the colorants are placed on the page. This is because the distributions of dots of the two or more colorants are not selected together to be visually pleasing.
The halftoning techniques of Blue Noise Mask and Void and Cluster Mask are known as point algorithms because the decision to place or not to place dots at a specific location (x, y) on an image plane depends only upon the color values at that location. With a grayscale image system using an 8-bit value to specify the grayscale image information and printing this image on a printer with a binary black printhead, the minimum grayscale value of 0 at a specific pixel location means that a dot should not be placed at the specific pixel location, and the maximum grayscale value of 255 at a pixel location means that a dot should be placed at the specific pixel location.
Each of the Blue Noise Mask and the Void and Cluster Mask consists of a large two-dimensional table of numbers, typically 128xc3x97128 or 256xc3x97256 square pixels, which are used to halftone full color images. The mask is tiled across a document so that every pixel location has associated with it a threshold value T(x, y) in the range of 0 to 255 from a mask or a matrix.
To decide whether or not to place a dot at a pixel location (x, y), the grayscale value of the image at that location, I(x, y), is compared against the threshold value T(x, y). If I(x, y) greater than T(x, y), a dot is placed at that location (x, y);
otherwise, a dot is not placed at that location. The values of T(x, y) are chosen so that for any grayscale value I between 0 and 255, a pleasing pattern of dots results over a wide area provided that the masks are properly constructed.
The construction of a Blue Noise mask is discussed in xe2x80x9cA Modified Approach to the Construction of a Blue Noise Mask,xe2x80x9d Dr. Kevin J. Parker, Journal of Electronic Imaging, January 1994. The construction of a Void and Cluster Mask is discussed in xe2x80x9cVoid and Cluster Halftoning Technique,xe2x80x9d Robert Ulichney, Proceedings of the SPIE, Febuary 1993.
These masks have been used in several different ways to halftone color images. To correlate two colorants q and r, for example, at a pixel location (x, y), the image values Iq(x, y) and Ir(x, y) are compared against the same threshold value T(x, y). To decorrelate the two colorants q and r, one image value Iq(x, y) is compared against the threshold value T(x, y) in the same manner as when correlating the two colorants, but the second colorant image value is compared against a different or inverted threshold value T(x+a, y+b); this implies that the original mask used to halftone the colorant q is shifted a pixels in the x direction and b pixels in the y direction to halftone the colorant r. To anticorrelate the two colorants q and r, one colorant image value Iq(x, y) is compared against the threshold value T(x, y) in the same manner as when correlating the two colorants, but the second colorant image value Ir(x, y) is compared against a different threshold value 255xe2x88x92T(x, y).
In general, when halftoned by each of these three techniques, the pattern of dots for each individual colorant is visually pleasing. However, the pattern of dots formed by combining the dots of each of the color planes is not necessarily visually pleasing because no effort is made to insure that the dots of each of the different color planes are distributed relative to the dots of the other color planes. Examples of producing a color composed of two colorants with each of these three methods follow.
Table 1 is assumed to represent an 8xc3x978 square pixel mask for either a Blue Noise mask or a Void and Cluster mask.
A grayscale, binary, printing process forms a black and image by either placing a dot or not placing a dot of black ink at each printable pixel location. An input value of I=0 at a location (x, y) represents the lightest printable color, which is produced by printing no dot at the location (x, y). An input value of I=255 at the pixel location (x, y) represents the darkest printable color black, which is produced by printing a dot at location (x, y).
Shades of gray other than white or black cannot be produced at the pixel location by this printing process since at each location a dot is either printed or not printed. Therefore, the shades of gray must be simulated by printing a pattern of dots over a wider area than just one pixel.
Accordingly, an input shade of gray having a value of I is produced over a selected area by printing a dot at each location of the selected area with a probability of I/255. On average, I dots out of every 255 locations are printed. If the selected area is too small, it may be impossible to place exactly on average I dots out of 255 locations over this area. Therefore, the shade of gray is not accurately reproduced but only approximated. This accounts for much of the loss of detail of a full-color image when printed on binary devices.
It should be noted that the threshold values in Table 1 are uniformly distributed with the threshold values spaced every four units from 0 to 252. The threshold values of Table 1 can be used to govern the probability of a dot being printed.
For example, if a gray level value of I=33 is to be produced over an entire 8xc3x978 square pixel area with the threshold values given by Table 1, nine dots will be printed at the positions having threshold values of 0, 4, 8, 12, 16, 20, 24, 28, and 32. Therefore, the gray level value of I=33 is approximated by 9 dots out of 64 where {fraction (9/64)} locations is approximately equal to {fraction (33/255)}. The nine dots are placed at the locations marked by X in Table 2. It is assumed that Table 2 was constructed so that this pattern of nine dots is a desirable arrangement of nine dots for a gray level value of I=33.
If a color is to be produced by a two color printing process employing cyan and magenta inks, for example, the color coordinates are specified by an ordered pair (C, M) where C and M specify the relative amounts of cyan and magenta colorants, respectively, to be placed at a pixel position in a range from 0 to 255. For example, if the color I=(23, 10) is to be produced over an entire 8xc3x978 square pixel area, the threshold values of Table 1 are used initially to produce a correlated pattern of dots to produce this color. Table 1 is used to threshold both colorants; this results in cyan dots being placed at the locations marked c and magenta dots being placed at the locations marked m in Table 3, which shows a correlated pattern of cyan and magenta dots for color (C, M)=(23, 10).
For this particular color, there are fewer magenta dots than cyan dots. Thus, the magenta dots are placed only at locations where there are also cyan dots when the color planes are correlated. This has the disadvantage that the blue dots, which result from placing both the cyan and magenta dots at the same pixel location, are more visually perceptible than the individual cyan or magenta dots.
If this color is produced by a decorrelated pattern of dots, the cyan dots are placed by comparing with the threshold values of Table 1 whereas the magenta dots are placed by comparing with the threshold values of Table 4, which is formed by shifting Table 1 a distance of a=4 pixels in the x direction and b=4 pixels in the y direction. The threshold values are xe2x80x9cwrapped aroundxe2x80x9d from right to left and top to bottom when shifted. Other values of a and b could be used, if desired.
The pattern of dots resulting from thresholding the value Cyan=23 against the values in Table 1 and Magenta=10 against the values in Table 4 is shown in Table 5, which shows a decorrelated pattern of cyan and magenta dots for color (C, M)=(23, 10).
The pattern of cyan dots is optimal since it is formed from a mask that was made to produce a pleasing pattern of dots for one colorant for any number of dots. The same is true for the pattern of magenta dots since it is formed from a shifted version of a mask that was prepared to produce a pleasing pattern of dots for one colorant, and shifting a mask with xe2x80x9cwrap aroundxe2x80x9d does not damage the ability of a mask to produce a pleasing pattern of dots. However, the pattern of dots resulting from combining the decorrelated cyan and magenta dots is not generally pleasing.
If the color I=(23, 10) is produced by an anticorrelated pattern of dots, each of the cyan dots is placed by comparing its value with the threshold value T(x, y) while each of the magenta dots is placed by comparing its value with the threshold value Txe2x80x2 (x, y)=255xe2x88x92T(x, y). Since this example uses a small 8xc3x978 square pixel mask and the largest value in this small mask is 252, the threshold values of Txe2x80x2 (x, y) are formed by subtracting the threshold values T(x, y) from 252 instead of 255. The threshold values of T(x, y) are shown in Table 1, and the threshold values Txe2x80x2 (x, y) are shown in Table 6.
The pattern of dots resulting from thresholding the value of cyan=23 with Table 1 and the value of magenta=10 with Table 6 is shown in Table 7, which shows an anticorrelated pattern of cyan and magenta dots for color (C, M)=(23, 10).
Although the individual cyan and magenta dot patterns will again be pleasing, the combined pattern of dots produced by combining the anticorrelated cyan and magenta dots is not generally pleasing.
The halftoning technique of error diffusion is generally attributed to Robert Floyd and Louis Steinberg as set forth in xe2x80x9cAn Adaptive Algorithm for Spatial Gray Scale,xe2x80x9d 1975 SID International Symposium, Digest of Technical Papers, pp. 36-37. This algorithm is unlike the Blue Noise mask and the Void and Cluster mask in that the decision to place or not to place a dot at a given location (x, y) depends on the image values at other pixel locations.
If a black-and-white image having image values of I(x, y) is to be printed on a binary printer, assume that each pixel has associated with it a threshold value T which is invariant for x and y values. If I(x, y) equals only either 0 or 255, the image can be reproduced as intended since not printing a dot corresponds to printing a value of I=0 while printing a dot corresponds to printing a value of I=255.
The problem occurs when I(x, y) is not equal to 0 or 255 for some x and y location; this is usually the situation with items such as photographs, for example. In this situation, printing or not printing a dot causes there to be an error from the intended colorant value. If a dot is placed at a position (x, y), an error equal to the amount of 255xe2x88x92I(x, y) is generated at the position (x, y). If a dot is not placed, an error equal to the amount I(x, y) is generated at the position (x, y).
The error diffusion algorithm calculates the error at a specific position as the result of quantization and diffuses this error to neighboring dots. If a dot is printed at the position (x, y), some amount of the error is subtracted from neighboring dots to decrease their probability of being printed to compensate for overprinting at the position (x, y). Similarly, if a dot is not printed at the position (x, y), some amount of the error is added to neighboring dots to increase their probability of being printed to compensate for underprinting at the position (x, y). The algorithm proposed by Floyd and Steinberg spreads {fraction (7/16)} of the error generated at the position or location (x, y) to a location (x+1, y), {fraction (3/16)} to a location (xxe2x88x921, y+1), {fraction (5/16)} to a location (x,y+1), and {fraction (1/16)} to a location (x+1, y+1).
When the value I(x, y) is between 0 and 255, this value can be thought of as the number of dots out of 255 to printed. If I(x, y) is constant over a wide area, on average, I(x, y) dots out of 255 will be printed in this area.
Numerous enhancements have been suggested to enhance the output quality of error diffusion. These include varying the threshold value by some amount as a function of x and y, varying the order in which pixels are quantized, and varying the amount of error spread to neighboring pixels as well as the choice of pixels to which the error is spread. Additionally, error diffusion has been extended to output devices that can produce multiple levels of a given colorant.
When used to print color images, the Blue Noise mask, the Void and Cluster mask, and the error diffusion technique have traditionally been applied independently to individual color planes. As previously mentioned for the Blue Noise mask and the Void and Cluster mask, individual color planes can have pleasing patterns of dots, but the combined dot pattern from multiple color planes is not generally pleasing.
Traditional color error diffusion for a two color printing process using cyan and magenta dots can be expressed as follows:
if (Cyan(x, y)+Cyan Error(x, y) greater than Threshold)
{
print Cyan dot
CError=255xe2x88x92(Cyan(x, y)+Cyan Error(x, y))
}
else
{
CError=0xe2x88x92(Cyan(x, y)+Cyan Error(x, y))
}
Cyan Error(x+1, y)=Cyan Error(x+1, y)xe2x88x92CError*{fraction (7/16)}
Cyan Error(xxe2x88x921, y+1)=Cyan Error(xxe2x88x921, y+1)xe2x88x92CError*{fraction (3/16)}
Cyan Error(x, y+1)=Cyan Error(x, y+1)xe2x88x92CError*{fraction (5/16)}
Cyan Error(x+1, y+1)=Cyan Error(x+1, y+1)xe2x88x92CError*{fraction (1/16)}
if (Magenta (x, y)+Magenta Error (x, y) greater than Threshold)
{
print Magenta dot
MError=255xe2x88x92(Magenta(x, y)+Magenta Error(x, y))
}
else
{
MError=0xe2x88x92(Magenta(x, y)+Magenta Error(x, y))
}
Magenta Error(x+1, y)=Magenta Error(x+1, y)xe2x88x92MError*{fraction (7/16)}
Magenta Error(xxe2x88x921, y+1)=Magenta Error(xxe2x88x921, y+1)xe2x88x92MError*{fraction (3/16)}
Magenta Error(x, y+1)=Magenta Error(x, y+1)xe2x88x92MError*{fraction (5/16)}
Magenta Error(x+1, y+1)=Magenta Error(x+1, y+1)xe2x88x92MError*{fraction (1/16)}
U.S. Pat. No. 5,210,602 to Mintzer describes a method of coupled-color error diffusion involving communication between several color planes of a color printing process. A first color plane is processed as previously described. That is, the sum of the input colorant value for the first color plane at a position (x, y) and the error propagated in the same plane to the pixel at the same position (x, y) is generated and sent to a quantizer which chooses an output pixel value closest to this sum. After quantization of the pixel at the location (x, y) in the first color plane, an error value is computed and propagated to neighboring pixels in the first color plane.
A second color plane is processed in a similar manner in that the sum of the original colorant value for the second colorant at a position (x, y) and the error propagated in the same color plane to the pixel at the same location (x, y) is generated as before, but some fraction of the error at the position (x, y) in the first color plane is added to this sum prior to quantization. If a dot is placed at the position (x, y) in the first color plane, the fraction of the error generated at this position in the first color plane and passed to the second color plane has the effect of reducing the probability of printing a dot in the second color plane at this position. If a dot is not placed at the position (x, y) in the first color plane, the fraction of the error generated at this position in the first color plane and passed to the second color plane has the effect of increasing the probability of printing a dot in the second color plane at this position.
This method fails to employ the mechanisms of error diffusion that produce a pleasing pattern of some number of dots in a single color plane to produce a pleasing pattern of some number of dots that reside in multiple color planes. The algorithm in the aforesaid Mintzer patent fails to take into consideration the total number of dots to be placed when processing the first color plane. Thus, when processing the second color plane, quantization is biased by results from the first color plane, but the first color plane is processed without any influence from the second color plane. That is, the dots are placed optimally in the first color plane for the first color plane only without regard to the overall pattern of dots to be produced in the multiple color planes.
The present invention overcomes the foregoing problems by considering the combined number of dots from the color planes when determining the number of dots of each of the color planes and their locations for the output pattern to be made visually pleasing.
This invention eliminates the disadvantage of placing dots of different colors on top of one another with correlated color halftoning as shown in Table 3 or the disadvantage of the displeasing combined pattern of cyan and magenta dots that results from decorrelated or anticorrelated color halftoning as shown in Tables 5 and 7, respectively. In each of Tables 5 and 7, the six cyan dots and the three magenta dots were placed for a total of nine dots.
Table 2 shows a visually pleasing pattern of nine dots, none of which is placed in the same pixel location. If it is desired to produce the color having a value of 33 (the sum of C=23 and M=10) of six cyan dots and three magenta dots, a pleasing pattern of nine dots is formed by comparing a value of 33 (the sum of C=23 and M=10) with each of the threshold values of the matrix.
When producing the color (C, M)=(23, 10), the output dot level 33 could be formed by adding the values C and M. This enables a decision to be made as to where each of the total of the nine cyan and magenta dots should be placed and leaves only determination at which of these nine locations that the six cyan dots and the three magenta dots are to be placed. The six cyan dots are placed by comparing the cyan colorant value against the threshold matrix of Table 1, and the three magenta dots are located at the remaining positions of the nine at which cyan dots were not placed. The resulting, visually pleasing pattern of six cyan and three magenta dots pattern is shown in Table 8.
If the total number of the cyan and magenta dots is larger than 255, some of the cyan and magenta dots must be placed at the same location and form blue dots. If the resulting blue dots are more visually perceptible than the individual cyan dot or the individual magenta dot, it is desired to produce a pleasing pattern of these blue dots.
In a manner similar to that just described, B, the number of the blue dots is compared to the threshold values of Table 1. Wherever the value of B is greater than the threshold value, both a cyan dot and a magenta dot are placed.
The number of pixels at which only the cyan dots are to be placed is Cxe2x80x2 where Cxe2x80x2=Cxe2x88x92B, and the number of pixels at which only the magenta dots are to be placed is Mxe2x80x2 where Mxe2x80x2=Mxe2x88x92B. To fill in the remaining pixels, the cyan dots are placed only wherever the value C is greater than the threshold values of Table 1 and a blue dot is not placed. The magenta dots are placed in the remaining vacant pixel locations. This causes a total of C cyan dots to be placed with B of the cyan dots being placed with the magenta dots and Cxe2x80x2 of the cyan dots being placed alone. A total of M magenta dots also will be placed, B of which are also placed with the cyan dots and Mxe2x80x2 of which are placed alone.
Accordingly, this invention eliminates the disadvantages of the previously available mechanisms of error diffusion for printing colors.
An object of this invention is to combine different halftoned color planes in a visually pleasing arrangement.
Another object of this invention is to provide an apparatus and method for producing a halftoned color image.
Other objects of this invention will be readily perceived from the following description, claims, and drawings.